#include <iostream>
using namespace std;
#define maxsize 50

// 希尔排序 -- 它通过将数组按照一定的间隔（gap）分成多个子序列，对每个子序列进行插入排序，逐步缩小间隔，直到间隔为 1 时，整个数组就基本有序了
void shellsort(int arr[], int n)
{
  int temp;
  
  // 遍历每一种幅度的间隔
  for (int gap = n / 2; gap > 0; gap /= 2)
  {
    // 对每一种间隔进行插入排序
    for (int i = gap; i < n; ++i)
    {
      // 暂存
      temp = arr[i];
      int j = i;
      
      // 找到插入位置
      while (j >= gap && arr[j - gap] > temp)
      {
        // 元素后移
        arr[j] = arr[j - gap];
        j -= gap;
      }
      
      // 插入
      arr[j] = temp;

      cout << endl;
    }
  }
}

int main()
{
  // 创建数组
  int A[] = {12, 6, 9, 2, 4};
  
  // 希尔排序
  shellsort(A, 5);
  
  // 打印
  for (int i = 0; i < 5; i++)
  {
    cout << A[i] << ' ';
  }
  return 0;
}